1. Field of the Invention
The present invention relates to an error correcting device and, more particularly, to the realization of its high processing speed.
2. Related Background Art
In an error correcting device using what is called a program control system in which error correcting processes are executed by a microprocessor or the like in accordance with a predetermined program, a discrimination of a jump (shift of the process) of the program and a change in count value of a program counter in association with the program jump are executed each time the result of the discrimination is obtained.
A conventional procedure of the processes will now be described with respect to the syndrome discrimination of the Reed Solomon code as an example. The Reed Solomon code is a multi-dimension block code of a cyclic type and, in recent years, it has been applied to various fields and has widely been known.
A decoding method of the Reed Solomon code having a code length (n) and (k) information symbols and comprising (n-k) check symbols will now be described. It is also assumed that each symbol is an element of a Galois field GF (2.sup.m), a finite field having m binary bits (i.e., 2.sup.m elements).
In this case, a generating polynomial g(x) of the (t)-ply error correction Reed Solomon code is expressed by the following equation (1) or (2) in which (.alpha.) is a primitive element of the Galois field GF (2.sup.m). EQU g(x)=(x+.alpha.) (x+.alpha..sup.2) . . . (x+.alpha..sup.2t) (1) EQU g(x)=(x+.alpha..sub.O) (x+.alpha.) . . . (x+.alpha..sup.2t-1) (2)
On the other hand, when a transmission code word is expressed by C(x) and a reception code word is expressed by R(x) and an error polynomial is expressed by E(x), the following relation is satisfied among them. EQU R(x)=C(x)+E(x) (3)
In this case, the coefficients of the polynomial are included in the Galois field GF (2.sup.m) and the error polynomial E(x) includes only the terms corresponding to the error location and a value (size).
Therefore, assuming that an error value at a position x.sub.j is set to Y.sub.j. ##EQU1## In the equation (4), .SIGMA.denotes the sum of errors at all positions.
Assuming that the syndromes S.sub.i are defined as follows EQU S.sub.i =R(.alpha..sup.i) [where, i=0, 1 . . . 2t-1] (5)
from the equation (3), EQU S.sub.i =C(.alpha..sup.i)+E(.alpha..sup.i)
In this case, since C(x) can always be divided by g(x), EQU C(.sup..alpha.i)=0 EQU Therefore, EQU S.sub.i =E(.alpha..sup.i)
From the equation (4), the syndromes can be expressed as follows. ##EQU2## However, it is assumed that .alpha..sup.j =X.sub.j and X.sub.j denotes an error location in the case of .alpha..sup.j.
When the number of errors is set to e, an error location polynomial .sigma.(x) is defined as follows. ##EQU3##
The following relation is provided between .sigma..sub.1 to .sigma..sub.e in the equation (7) and the syndromes S.sub.i. EQU S.sub.i+e +.sigma..sub.1 S.sub.i+e-1 +. . . .sigma..sub.e-1 S.sub.i+1 +.sigma..sub.e S.sub.i ( 8)
Namely, the above Reed Solomon code is decoded in the following procedure.
(I) The syndromes S.sub.i are calculated by the equation (5). PA1 (II) The coefficients .sigma..sub.1 to .sigma..sub.e of the error location polynomial are calculated by the equation (8). PA1 (III) A root X.sub.j of the error location polynomial is obtained by the equation (7). PA1 (IV) The error value Y.sub.j is obtained by the equation (6) and the error polynomial is obtained by the equation (4). PA1 (V) The error correction is executed by the equation (3).
A practical example of the error correction by the decoding procedure as mentioned above will now be described with respect to the case where four check symbols are used in one-block data.
That is, the generating polynomial g(x) in this case is as follows. ##EQU4## The correction until the double error can be corrected.
The case of actually executing the error correction will now be considered with respect to the following four cases: e=0; e=1, e=2, and e.gtoreq.3. When e=0, this means that the received message word is correct, so that no error correcting process is executed. On the other hand, when e.gtoreq.3, this also means that such a case exceeds the error correcting capability, so that the error correcting process other than the process to set an error flag into 1 is not executed. That is, the error correcting process is actually executed only in the cases where e=1 and e=2.
The error correcting process is schematically executed by the following procedure in correspondence to the above decoding procedures (I) and (II).
(a) The syndromes S.sub.0 to S.sub.3 are calculated.
(b) The syndromes S.sub.0 to S.sub.3 are checked and when S.sub.0 =S.sub.1 =S.sub.2 =S.sub.3 =0, it is determined that e=0 and the error correcting process is finished. Further, when only one of the values of the syndromes S.sub.0 to S.sub.3 is equal to 0, this means that e.noteq.1. When any two or more of the values of the syndromes S.sub.0 to S.sub.3 are equal to 0, it will be obvious from the equation (6) that e.gtoreq.3.
(c) When the equation (8) is rewritten with respect to e=1 and e=2.
in the case where e=1. ##EQU5##
and in the case where e=2. ##EQU6##
It is now assumed that the actual decoder starts the operation from the case where e=1. Then, the solution .sigma..sub.1 which satisfies the simultaneous equation (9) must be first obtained. If such a solution does not exist, the decoder must obtain the solutions .sigma..sub.1 and .sigma..sub.2 which satisfy the simultaneous equation (10) with respect to the case of e=2. If no solution is derived here, it can be regarded such that e.gtoreq.3.
The solution .sigma..sub.1 of the equation (9) is obtained as follows. ##EQU7## The solutions .sigma..sub.1 and .sigma..sub.2 of the equation (10) are obtained as follows. ##EQU8##
In the above procedures, the values of the various equations are calculated and compared in each step. It is then necessary to change the program flow indicative of the processing in accordance with the result of the discrimination.
For instance, the number e of errors can be determined as shown in Table 1 in accordance with the values of the syndromes S.sub.0 to S.sub.3 in the step (b).
TABLE 1 ______________________________________ S.sub.0 S.sub.1 S.sub.2 S.sub.3 e ______________________________________ =0 =0 =0 =0 =0 =0 =0 =0 .noteq.0 .gtoreq.3 =0 =0 .noteq.0 =0 .gtoreq.3 =0 =0 .noteq.0 .noteq.0 .gtoreq.3 =0 .noteq.0 =0 =0 .gtoreq.3 =0 .noteq.0 =0 .noteq.0 .gtoreq.3 =0 .noteq.0 .noteq.0 =0 .gtoreq.3 =0 .noteq.0 .noteq.0 .noteq.0 .gtoreq.2 .noteq.0 =0 =0 =0 .gtoreq.3 .noteq.0 =0 =0 .noteq.0 .gtoreq.3 .noteq.0 =0 .noteq.0 =0 .gtoreq.3 .noteq.0 =0 .noteq.0 .noteq.0 .gtoreq.2 .noteq.0 .noteq.0 =0 =0 .gtoreq.3 .noteq.0 .noteq.0 =0 .noteq.0 .gtoreq.3 .noteq.0 .noteq.0 .noteq.0 =0 .gtoreq.3 .noteq.0 .noteq.0 .noteq.0 .noteq.0 .gtoreq.1 ______________________________________
An outline of the flow of the processes according to the determination is shown in a flowchart of FIG. 1. The step shown by "e.gtoreq.3" in FIG. 1 denotes that the number of errors is decided to be 3 or more and that the processing routine advances to the processing routine for the excessive error correcting capability. The step shown by "e.gtoreq.2" denotes that the number of errors is decided to be 2 or more and that the processing routine advances to the processing routine for correction of double error. Further, the step shown by "e.gtoreq.1" denotes that the number of errors is decided to be 1 or more and that the processing routine advances to the processing routine for correction of single error.
On the other hand, consider the following as one example in which the flow of the program is changed as mentioned above, that is, the program is jumped. When the coefficients .sigma..sub.1 and .sigma..sub.2 of the error location polynomial are calculated in the foregoing step (c), checks are made to see if the denominator (S.sub.1 .sup.2 +S.sub.0 S.sub.2) and the numerators (S.sub.0 S.sub.3 +S.sub.1 S.sub.2) and (S.sub.1 S.sub.3 +S.sub.2.sup.2) are equal to 0 and the program is jumped in accordance with the results of the discriminations. That is, when the denominator (S.sub.1.sup.2 +S.sub.0 S.sub.2) is equal to 0, the processing routine advances to the processing routine for the excessive error correcting capability. When either one of the numerators (S.sub.0 S.sub.3 +S.sub.1 S.sub.2) and (S.sub.1 S.sub.3 +S.sub.2.sup.2) is equal to 0, the processing routine advances to the processing routine for correction of single error.
However, in the above conventional example using S.sub.0, S.sub.1 and S.sub.2 for discrimination rather than .sigma.1 and .sigma.2, for instance, assume that the program is jumped in the case where the result of the discrimination is "Yes" ("Y") in each of the discriminating step in the flowchart of FIG. 1. It is then necessary to jump the program one or two times until the processing routine advances to the double-error correction processing routine through the step shown by "e.gtoreq.2". It is necessary to jump the program about four times until the processing routine advances to the no-error processing routine through the step shown by "e=0". Moreover, it will be obvious from FIG. 1 that a fairly large program step area is needed to describe the above programs.
On the other hand, even in the procedure to calculate the coefficients .sigma..sub.1 and .sigma..sub.2 of the above error location polynomial, there is also an increase in the program step area increases. Even in the case of sequentially executing the steps of checking to see if (S.sub.1.sup.2 +S.sub.0 S.sub.2), (S.sub.0 S.sub.3 +S.sub.1 S.sub.2), and (S.sub.1 S.sub.3 +S.sub.2.sup.2) are equal to 0 or not, the program step area also similarly increases.
As mentioned above, when the program step area increases and the possibility of the program jump increases, it takes time to execute the above programs so that processes cannot be performed at high speed. Thus, it is difficult to process the received message of a high bit rate.